export type TGraphAdjacentMatrix<L> = Tuple2DimEL<L, number>;

const INF = Infinity;
const minDistance = (dist, visited) => {
  let min = INF;
  let minIndex = -1;
  
  for (let v = 0; v < dist.length; v++) {
    if (visited[v] === false && dist[v] <= min) {
      min = dist[v];
      minIndex = v;
    }
  }

  return minIndex;
};
export const dijcstra = <Length extends number>(graph: TGraphAdjacentMatrix<Length>, src: number) => {
  const dist: number[] = [...(graph[src] ?? [])];
  const paths: {
    [props: string]: string
  } = {
    [src]: `${src}`
  };
  const visited: boolean[] = [];
  const { length } = graph;

  for (let i = 0; i < dist.length; i++) {
    if (dist[i] === 0 && i !== src) {
      dist[i] = INF;
      paths[i] = `${src}`;
    } else {
      paths[i] = `${src} -> ${i}`;
    }
    visited.push(false);
  }

  for (let i = 0; i < length; i++) {
    const minIndex = minDistance(dist, visited);
    visited[minIndex] = true;
    
    for (let mi = 0; mi < length; mi++) {
      if (!visited[mi] && graph[minIndex][mi] !== 0 && dist[minIndex] !== INF && dist[minIndex] + graph[minIndex][mi] < dist[mi]) {
        dist[mi] = dist[minIndex] + graph[minIndex][mi];
        paths[mi] = paths[minIndex] + ` -> ${mi}`;
      }
    }
  }
  
  return {
    paths,
    dist
  };
};
